#include "greedy.h"
#include <iostream>
#include <set>
#include <iomanip>
#include <random>
#include <chrono>

using namespace std;


struct Seq{
  vector<int> pso;
  int val;
  Seq(){}
  Seq(int _v, vector<int> &_p):val(_v),pso(_p){}
  bool operator<(const Seq& other) const { return val < other.val;}
};

int epoch=30, group_num=1000, n=40, relax_coe = 2;
float mutation_line = 0.6; 
vector<Seq> real_group[2];
int flag=0;
Data *dataset;

int calc(vector<int>& order) {
  auto solver = Greedy(dataset,order);
  return solver.solve();
};
void init_group() {
  vector<Seq>& group = real_group[flag];
  group.reserve(group_num);
  std::vector<int> order;
  order.reserve(40);
  for(int i=20;i<40;i++) order.push_back(i);
  for(int i=0;i<20;i++) order.push_back(i);
  auto tmp_value = calc(order);
  group.emplace_back(tmp_value,order);

  std::random_device rd;
  std::mt19937 g(rd());
  while (group.size()<group_num) {
    std::vector<int> new_order = order;
    shuffle(new_order.begin(),new_order.end(),g);
    auto tmp_value = calc(new_order);
    group.emplace_back(tmp_value,new_order);
  }
}

Seq variation(Seq &t) {
  Seq output;
  int idx = rand() % n, idy = rand() %n;
  if (idx>idy) swap(idx,idy);
  assert(idx<=idy);
  output.pso = t.pso;
  for(;idx<=idy;idx++,idy--)
    swap(output.pso[idx],output.pso[idy]);
  output.val = calc(output.pso);
  return std::move(output);
}
pair<Seq,Seq> cross(Seq &t1, Seq &t2){
  Seq output1, output2;
  output1.pso.reserve(n);
  output2.pso.reserve(n);
  set<int> st;
  for (int i = 0; i < n/2; i++){
    st.insert(t1.pso[i]);
    output1.pso.push_back(t1.pso[i]);
  }
  for (int i = 0; i < n; i++) {
    if (st.find(t2.pso[i])==st.end()) {
      output1.pso.push_back(t2.pso[i]);
    } else {
      output2.pso.push_back(t2.pso[i]);
    }
  }
  for (int i = n/2; i < n; i++){
      output2.pso.push_back(t1.pso[i]);
  }
  assert(output1.pso.size()==n && output2.pso.size()==n);
  output1.val = calc(output1.pso);
  output2.val = calc(output2.pso);

  return make_pair(std::move(output1),std::move(output2));
}
vector<int> run() {
  init_group();
  int history_best = int(1e7);
  Seq best_order;
  auto start_time = std::chrono::system_clock::now();
  for(int i=0;i<epoch;i++) {
    vector<Seq>& group = real_group[flag];
    vector<Seq>& new_group = real_group[1-flag];
    int epoch_best=100000,epoch_avg=0;
    for(int j=0;j<group_num;j++) {
      epoch_avg+=group[j].val;
      epoch_best = min(epoch_best, group[j].val);
      if (group[j].val < history_best) {
        history_best = group[j].val;
        best_order = group[j];
      }
    }
    cout<<"["<<duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - start_time).count()/1000<<"s]\t";
    cout<<"epoch-"<<i<<"\t";
    cout<<"epoch_avg-"<<fixed<<setprecision(2)<<epoch_avg/group_num<<",";
    cout<<"epoch_best-"<<fixed<<setprecision(2)<<epoch_best<<",";
    cout<<"history_best-"<<fixed<<setprecision(2)<<history_best<<".";
    cout<<endl;
    new_group.clear();
    while (new_group.size() < relax_coe * group_num) {
      if ((rand()%10)/10.0 < mutation_line) {
        auto out = variation(group[rand()%group_num]);
        new_group.push_back(std::move(out));
      } else {
        auto out = cross(group[rand()%group_num], group[rand()%group_num]);
        new_group.push_back(std::move(out.first));
        new_group.push_back(std::move(out.second));
      }
    }
    sort(new_group.begin(),new_group.end());
    if (new_group.size()>group_num) 
      new_group.erase(new_group.begin()+group_num,new_group.end());
    flag = 1-flag;
  }
  return best_order.pso;
}

int main() {
  string file_path = "data/sol.csv";
  dataset = new Data();
  srand(time(0));
   vector<int> zero{20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
                   30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
                   0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
                   10, 11, 12, 13, 14, 15, 16, 17, 18, 19};
  // auto solver = Greedy(data,zero);
  // cout<<solver.solve()<<endl;
  // cout<<solver<<endl;

  // GA
  cout<<"=================Genetic begin=============="<<std::endl;
  auto best_order = run();
  cout<<"=================Genetic end==============\""<<std::endl;
  // Greedy
  auto greed = Greedy(dataset, best_order);
  cout<<greed.solve()<<endl;
  cout<<greed<<std::endl;
  ofstream file_out;
  file_out.open(file_path, ios::out);
  file_out<<greed;
  return 0;
}